#include <vector>

using namespace std;
// 思路： 使用深度优先搜索（DFS）来探索所有可能的组合。
class Solution
{
public:
    vector<vector<int>> combinationSum(vector<int> &candidates, int target)
    {
        vector<int> temp;
        vector<vector<int>> res;
        dfs(res, temp, target, candidates, 0);
        return res;
    }
    // 深度优先搜索函数
    // res: 存储所有符合条件的组合
    // temp: 当前组合
    // target: 剩余目标和
    // candidates: 候选数字列表
    // start: 当前搜索的起始索引
    void dfs(vector<vector<int>> &res, vector<int> &temp, int target, vector<int> &candidates, int start)
    {
        if (target == 0) // 找到一个符合条件的组 合
        {
            res.push_back(temp);
            return;
        }
        if (target < 0) // 超过目标和，终止搜索
            return;
        for (int i = start; i < candidates.size(); ++i) // 遍历候选数字 为什么是从start开始？ 因为可以重复使用同一个数字
        {
            temp.push_back(candidates[i]);
            // 为什么是i而不是i+1？ 因为可以重复使用同一个数字
            dfs(res, temp, target - candidates[i], candidates, i); // 继续递归搜索，注意这里传入的是i而不是i+1
            temp.pop_back();
        }
    }
};